package com.duoduo.双指针;

/**
 * @author dl.chai
 * @version 1.0
 * @description: 寻找重复数287
 * 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
 * <p>
 * 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
 * <p>
 * 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,3,4,2,2]
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：nums = [3,1,3,4,2]
 * 输出：3
 * @date 2023/3/24 17:05
 */

public class 寻找重复数287 {
    public int findDuplicate(int[] nums) {
        //采用双指针解法，在这里给两组数，以便于后期复习理解
        //1342 形成一个环形链表为：0->1->3->2->4->null  这时候就没有重复的数字
        //13422 形成一个环形链表为：0->1->3->2->4->2->4->2->2  这时候2->4就形成了循环，此时在2的时候重复了，坐标为4
        int slow = 0;
        int fast = 0;
        slow=nums[slow];//1
        fast = nums[nums[fast]];//3
        //1!=3  这里这样写是因为题目中已经说了，一定会有重复的数字，如果没有，这里会形成死循环，工作中可不能这样写
        while (fast != slow) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        //这里出来的时候就是坐标为4的时候
        int pre1=0;
        int pre2=slow;
        while (pre1!=pre2){
            pre1=nums[pre1];
            pre2=nums[pre2];
        }
        //到这里出来的时候就是2的时候
        return pre1;
    }

    public static void main(String[] args) {
        int duplicate = new 寻找重复数287().findDuplicate(new int[]{
                1, 3, 4, 2, 2
        });
        System.out.println(duplicate);
    }
}
